import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        int n= arr.length;
        int[][] dp=new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i],2);
        }
        Map<Integer,Integer> map=new HashMap<>();
        map.put(arr[0],0);
        int ans=2;
        for (int i = 1; i < n; i++) {
            //i是倒数第二个位置
            //j是倒数第一个位置
            for (int j = i+1; j < n; j++) {
                if(map.containsKey(arr[j]-arr[i])){
                    int k=map.get(arr[j]-arr[i]);
                    dp[i][j]=dp[k][i]+1;
                    ans=Math.max(dp[i][j],ans);
                }
            }
            map.put(arr[i],i);
        }
        return ans;
    }
}